package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

const N = 9

var solutions [][][]int // 用于存储所有找到的解
var solutionCount int

// 检查在 board[row][col] 填入 num 是否合法
func isValid(board [][]int, row, col, num int) bool {
	// 检查行
	for x := 0; x < N; x++ {
		if board[row][x] == num {
			return false
		}
	}

	// 检查列
	for x := 0; x < N; x++ {
		if board[x][col] == num {
			return false
		}
	}

	// 检查 3x3 宫格
	startRow := (row / 3) * 3
	startCol := (col / 3) * 3
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			if board[startRow+i][startCol+j] == num {
				return false
			}
		}
	}

	return true
}

// 回溯求解并收集所有解
func solveSudoku(board [][]int) {
	row, col := -1, -1
	isEmpty := true

	// 寻找一个未填的位置
	for i := 0; i < N; i++ {
		for j := 0; j < N; j++ {
			if board[i][j] == 0 {
				row, col = i, j
				isEmpty = false
				break
			}
		}
		if !isEmpty {
			break
		}
	}

	// 如果没有空格，则找到一个解
	if isEmpty {
		// 深拷贝当前 board，避免后续回溯修改它
		solution := make([][]int, N)
		for i := range board {
			solution[i] = make([]int, N)
			copy(solution[i], board[i])
		}
		solutions = append(solutions, solution)
		solutionCount++
		return
	}

	// 尝试填入数字 1~9
	for num := 1; num <= 9; num++ {
		if isValid(board, row, col, num) {
			board[row][col] = num
			solveSudoku(board)
			board[row][col] = 0 // 回溯
		}
	}
}

func main() {
	board := readSudoku()

	// 清空之前的解
	solutions = nil
	solutionCount = 0

	// 求解并收集所有解
	solveSudoku(board)

	// 输出结果
	fmt.Printf("🎯 该数独题目共有 %d 个解。\n\n", solutionCount)

	for idx, sol := range solutions {
		fmt.Printf("💡 解 %d：\n", idx+1)
		printSudoku(sol)
	}
}

func readSudoku() [][]int {
	return [][]int{
		{5, 3, 0, 0, 7, 0, 0, 0, 0},
		{6, 0, 0, 1, 9, 5, 0, 0, 0},
		{0, 9, 8, 0, 0, 0, 0, 6, 0},
		{8, 0, 0, 0, 6, 0, 0, 0, 3},
		{4, 0, 0, 8, 0, 3, 0, 0, 1},
		{7, 0, 0, 0, 2, 0, 0, 0, 6},
		{0, 6, 0, 0, 0, 0, 2, 8, 0},
		{0, 0, 0, 4, 1, 9, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
	}
}

// 打印一个数独解（9x9）
func printSudoku(solution [][]int) {
	for i := 0; i < N; i++ {
		if i%3 == 0 && i != 0 {
			fmt.Println("------+-------+------")
		}
		for j := 0; j < N; j++ {
			if j%3 == 0 && j != 0 {
				fmt.Print("| ")
			}
			fmt.Printf("%d ", solution[i][j])
		}
		fmt.Println()
	}
	fmt.Println()
}

// 读取用户输入的数独，支持 0 或 . 表示空格
func readSudoku_input() [][]int {
	board := make([][]int, N)
	fmt.Println("请输入数独题目（9行，每行9个数字，用空格分隔，空格用 0 或 . 表示）：")
	fmt.Println("例如：")
	fmt.Println("5 3 0 0 7 0 0 0 0")
	fmt.Println("6 0 0 1 9 5 0 0 0")
	fmt.Println("...（共9行，每行9个数字）")

	scanner := bufio.NewScanner(os.Stdin)
	for i := 0; i < N; i++ {
		board[i] = make([]int, N)
		scanner.Scan()
		line := scanner.Text()
		fields := strings.Fields(line) // 按空格分割字段

		if len(fields) != N {
			fmt.Printf("❌ 第 %d 行必须输入 9 个数字（用空格分隔），但现在只有 %d 个。\n", i+1, len(fields))
			i-- // 重新输入这一行
			continue
		}

		for j := 0; j < N; j++ {
			c := fields[j]
			var num int
			if c == "." || c == "0" {
				num = 0
			} else {
				var err error
				num, err = strconv.Atoi(c)
				if err != nil || num < 0 || num > 9 {
					fmt.Printf("❌ 第 %d 行 第 %d 列的值 '%s' 不是有效的数独数字（应为 0/. 或 1~9）\n", i+1, j+1, c)
					j--
					continue
				}
			}
			board[i][j] = num
		}
	}
	return board
}
